package cn.kent.simple;

/**
 * 509. 斐波那契数
 * 注意审题，求得是F(3)=F(2)+F(1), 并不是F(3)=F(2)+F(1)+F(0)
 */
public class Fib {
    public static void main(String[] args) {
        System.out.println(fib(5));
    }

    /**
     * 动态规划
     * 1. 确定递推公式
     * 2. 确定边界条件
     * 3. 确定状态转移方程
     *
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int fib4(int n) {
        if (n < 2) return n;
        int p = 0, q = 0, r = 1;
        // 滚动数组思想
        for (int i = 2; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    /**
     * 递归 - 0ms
     */
    public static int fib(int n) {
        if (n <= 0) return 0;
        return fib(n, 1, 1);
    }

    private static int fib(int n, int lr, int llr) {
        if (n <= 2) return lr;
        return fib(n - 1, lr + llr, lr);
    }

    /**
     * 递归 - me
     */
    public static int fib3(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 加多了，F(4)=F(3)+F(2)+F(1)+F(0)
     */
    public static int fib2(int n) {
        if (n > 0) {
            int sum = 0;
            sum += fib(n - 1);
            return sum + (n - 1);
        }
        return 0;
    }
}
